package LC;

/**
 * https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/description/
 * Say you have an array for which the ith element is the price of a given stock on day i.
 * Design an algorithm to find the maximum profit. You may complete at most two transactions.
 * Note:
 * You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
 */
public class LC_123_BestTimetoBuyandSellStockIII_Greedy {
    public static void main(String[] args) {
        int maxProfit = Solution.maxProfit(new int[]{1, 2, 3, 4, 5});
        System.out.println(maxProfit);
    }

    static class Solution {
        static int maxProfit(int[] prices) {
            if (prices == null || prices.length <= 1) return 0;
            int len = prices.length;
            int maxProfit = 0;
            int min = prices[0];
            int arrayA[] = new int[len];
            for (int i = 1; i < prices.length; i++) {
                min = Math.min(min, prices[i]);
                arrayA[i] = Math.max(arrayA[i - 1], prices[i] - min);
            }
            int max = prices[len - 1];
            int arrayB[] = new int[len];
            for (int i = len - 2; i >= 0; i--) {
                max = Math.max(prices[i], max);
                arrayB[i] = Math.max(max - prices[i], arrayB[i + 1]);
            }
            for (int i = 0; i < len; i++) maxProfit = Math.max(maxProfit, arrayA[i] + arrayB[i]);
            return maxProfit;
        }
    }
}
